Mathematics PRINCIPLE OF MATHEMATICAL INDUCTION
Please Wait... While Loading Full Video

Class 11 Chapter 4 - principle of mathematical induction

PRINCIPLE OF MATHEMATICAL INDUCTION

Topics Covered

`star` Introduction
`star` Motivation
`star` The Principle of Mathematical Induction

Introduction

`\color{green} ✍️` One key basis for mathematical thinking is deductive reasoning. An informal, and example of deductive reasoning, borrowed from the study of logic, is an argument expressed in three statements:
`color{blue}((a))` `\color{green}" Socrates is a man."`

`color{blue}((b))` `\color{green}" All men are mortal, therefore, "`

`color{blue}((c))` `\color{green}" Socrates is mortal. "`

If statements `(a)` and `(b)` are true, then the truth of `(c)` is established.

To make this simple mathematical example, we could write :
`color{blue}((i))``\color{green}" Eight is divisible by two."`

`color{blue}((ii))` `\color{green}" Any number divisible by two is an even number,"`
therefore,

`color{blue}((iii))` `\color{green}" Eight is an even number."`

`\color{green} ✍️` In algebra or in other discipline of mathematics, there are certain results or statements that are formulated in terms of n, where n is a positive integer. To prove such statements the well-suited principle that is used–based on the specific technique, is known as `color{blue}(ul"the principle of mathematical induction.")``

Motivation

In mathematics, we use a form of complete induction called `color{green}ul "mathematical induction."`

`\color{green} ✍️` To understand the basic principles of mathematical induction, suppose a set of thin rectangular tiles are placed on one end, as shown in Fig.



When the first tile is pushed in the indicated direction, all the tiles will fall. To be absolutely sure that all the tiles will fall, it is sufficient to know that
`(a)` The first tile falls, and

`(b)` In the event that any tile falls its successor necessarily falls.


`\color{green} ✍️` This is the underlying principle of mathematical induction. We know, the set of natural numbers `N` is a special ordered subset of the real numbers. In fact, `N` is the smallest subset of `R` with the following property:

A set `S` is said to be an inductive set if `1∈ S` and `x + 1 ∈ S` whenever `x ∈ S.` Since `N` is the smallest subset of `R` which is an inductive set, it follows that any subset of `R` that is an inductive set must contain `N.`

The Principle of Mathematical Induction

Suppose there is a given statement `P(n)` involving the natural number `n` such that
`color{blue}((i))` The statement is `color{blue}(ul"true for")` `\color{green}(n = 1,)` i.e., `\color{green}(P(1))` is true, and

`color{blue}((ii))` If the statement is `color{blue}(ul"true for")` `\color{green}(n = k)` (where `k` is some positive integer),

then the statement is `color{blue}(ul"also true for")` `\color{green}(n = k+1)`, i.e., truth of `\color{green}(P(k))` implies the truth of `\color{green}(P(k+1))`.

Then, `\color{green}(P(n)` `color{blue}(ul"is true for all natural numbers n.")`

`color{blue} "Property (i)"` is simply a statement of fact. There may be situations when a statement is true for all `n ≥ 4.` In this case, step `1` will start from `n = 4` and we shall verify the result for `n = 4,` i.e., `P(4).`

`color{blue} "Property (ii)"` is a conditional property. It does not assert that the given statement is true for `n = k,` but only that if it is true for `n = k,` then it is also true for `n = k +1.` So, to prove that the property holds , only prove that conditional proposition:

If the statement is true for `n = k,` then it is also true for `n = k + 1.` This is sometimes referred to as the inductive step. The assumption that the given statement is true for `n = k` in this inductive step is called `color{blue}(ul"the inductive hypothesis.")`

`color{green} ("Example :" )` `color{blue}( "Sum of the first n odd natural numbers is the square of n.")`

Let us write

` \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \P(n): 1 + 3 + 5 + 7 + ... + (2n – 1) = n^2.`

The first step in a proof that uses mathematical induction is to prove that `P (1)` is true. This step is called `color{blue}( "the basic step.")`

Obviously ` \ \ \ \ 1 = 1^2,` i.e., `P(1)` is true.

The next step is called `color{blue}( "the inductive step.")`

Here, we suppose that `P (k)` is true for some positive integer `k` and we need to prove that `P (k + 1)` is true. Since `P (k)` is true, we have

` \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1 + 3 + 5 + 7 + ... + (2k – 1) = k^2 ................... (1)`

Consider
` \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1 + 3 + 5 + 7 + ... + (2k – 1) + {2(k +1) – 1} .......................... (2)`

` \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \= k^2 + (2k + 1) = (k + 1)^2 \ \ \ \ \ \ \ \ \ \ \ \ ["Using" (1)]`

Therefore, `P (k + 1)` is true and the inductive proof is now completed.

Hence `P(n)` is true for all natural numbers `n.`
Q 3125545461

For all n ≥ 1, prove that

`1^2 + 2^2 + 3^2 + 4^2 + ........+ n^2 = ( n (n+1) (2n +1) )/6`

Solution:

Let the given statement be P(n), i.e.,

`P(n) : 1^2 + 2^2 + 3^2 + 4^2 +…+ n^2 = ( n (n+1) (2n+1) )/6`

For n = 1, `P( 1 ): 1 = (1(1 + 1)(2 xx1 + 1) )/6 = (1 xx 2 xx 3)/6 = 1` which is true.

Assume that P(k) is true for some positive integers k, i.e.,

`1^2 + 2^2 + 3^2 + 4^2 +…+ k^2 = ( k (k+1) (2k+1) )/6` ............(1)

We shall now prove that P(k + 1) is also true. Now, we have

`(1^2 +2^2 +3^2 +4^2 +…+k^2 ) + (k + 1)^2`

`= ( k (k+1) (2k +1) )/6 + (k+1)^2` [Using (1)]

`= ( k (k+1) (2k+1) + 6 (k+1)^2 )/6`

`= ( (k+1) (2k^2 +7k + 6 ) )/6`

`= ( (k+1) (k+1+1) { 2 (k+1) +1} )/6`

Thus P(k + 1) is true, whenever P (k) is true.
Hence, from the principle of mathematical induction, the statement P(n) is true
for all natural numbers N.
Q 3155545464

Prove that `2^n > n` for all positive integers n.

Solution:

Let `P(n) : 2^n > n`

When `n =1, 2^1 > 1`. Hence P(1) is true.

Assume that P(k) is true for any positive integers k, i.e.,

`2k > k` ... (1)

We shall now prove that P(k +1) is true whenever P(k) is true.

Multiplying both sides of (1) by 2, we get

`2 * 2^k > 2k`

i.e., `2^(k + 1) > 2k = k + k > k + 1`

Therefore, P(k + 1) is true when P(k) is true. Hence, by principle of mathematical
induction, P(n) is true for every positive integer n.
Q 3115645560

For every positive integer n, prove that `7^n – 3^n` is divisible by 4.

Solution:

We can write
`P(n) : 7^n – 3^n` is divisible by 4.

We note that

`P(1): 7^1 – 3^1 = 4` which is divisile by 4. Thus P(n) is true for n = 1
Let P(k) be true for some natural number k,

i.e., `P(k) : 7^k – 3^k` is divisible by 4.

We can write `7^k – 3^k = 4d`, where d ∈ N.

Now, we wish to prove that P(k + 1) is true whenever P(k) is true.

Now `7^((k + 1)) – 3^((k + 1)) = 7^((k + 1)) – 7.3^k + 7.3^k – 3^((k + 1))`

`= 7(7^k – 3^k) + (7 – 3)3^k = 7(4d) + (7 – 3)3^k`

`= 7(4d) + 4.3^k = 4(7d + 3^k)`

From the last line, we see that `7^((k + 1)) – 3^((k + 1))` is divisible by 4. Thus, P(k + 1) is true
when P(k) is true. Therefore, by princlple of mathematical induction the statement is
true for every positive integer n.
Q 3175545466

For all n ≥ 1, prove that

` 1/(1*2) + 1/(2*3) + 1/(3*4) + .... + 1/(n ( n+1) ) = n/(n+1)` .


Solution:

We can write

`P(n ) : 1/(1*2) + 1/(2*3) +1/(3*4) + ...... + 1/(n (n+1) ) = n/(n+1)`

We note that `P(1) : =1/(1*2) =1/2 = 1/(1+1)`, which is true. Thus, P(n) is true for n = 1.
Assume that P(k) is true for some natural numbers k,

i.e., `1/(1*2) + 1/(2*3) + 1/(3*4) + .... + 1/(k (k+1) ) = k/(k+1)` ........(1)

We need to prove that P(k + 1) is true whenever P(k) is true. We have

`1/(1*2) + 1/(2*3) + 1/(3*4) + ...... + 1/(k (k+1) ) + 1/( (k+1) (k+2) )`

`= [ 1/(1*2) +1/(2*3) + 1/(3*4) + ..... + 1/(k (k+1) ) ] + 1/( (k+1) (k+2) )`

`= k/(k+1) + 1/( (k+1) ( k+2) )` [Using (1)]


` = (k (k+2) +1)/( (k+1) (k+2) ) = (k^2 + 2k +1 )/( (k+1) (k+2) ) = ((k+1)^2 )/( (k+1)(k+2) ) = (k+1)/(k+2) = (k+1)/( (k+1) +1 )`

Thus P(k + 1) is true whenever P(k) is true. Hence, by the principle of mathematical
induction, P(n) is true for all natural numbers.
Q 3135645562

Prove that `(1 + x)^n ≥ (1 + nx)`, for all natural number n, where x > – 1.

Solution:

Let P(n) be the given statement,

i.e., `P(n) : (1 + x)^n ≥ (1 + nx)` , for x > – 1.

We note that P(n) is true when n = 1, since ( 1+x) ≥ (1 + x) for x > –1

Assume that

`P(k) : (1 + x)^k ≥ (1 + kx), x > – 1` is true. ... (1)

We want to prove that P(k + 1) is true for x > –1 whenever P(k) is true. ... (2)
Consider the identity

`(1 + x)^(k + 1) = (1 + x)^k (1 + x)`

Given that x > –1, so (1+x) > 0.

Therefore , by using `(1 + x)^k ≥ (1 + kx)`, we have

`(1 + x)^(k + 1) ≥ (1 + kx)(1 + x)`

i.e. `(1 + x)^(k + 1) ≥ (1 + x + kx + kx^2)`. ... (3)

Here k is a natural number and `x^2 ≥ 0` so that `kx^2 ≥ 0`. Therefore

`(1 + x + kx + kx^2) ≥ (1 + x + kx)`,

and so we obtain

`(1 + x)^(k + 1) ≥ (1 + x + kx)`

i.e. `(1 + x)^(k + 1) ≥ [1 + (1 + k)x]`

Thus, the statement in (2) is established. Hence, by the principle of mathematical
induction, P(n) is true for all natural numbers.
Q 3115745660

Prove that

`1^2 + 2^2 + .... + n^2 > n^3/3 , n ∈ N`

Solution:

Let P(n) be the given statement.

i.e., `P(n) : 1^2 + 2^2 + ... + n^2 > n^3/3 , n ∈ N `


We note that P(n) is true for n = 1 since `1^2 > 1^3/3`


Assume that P(k) is true

i.e., `P(k) : 1^2 + 2^2 + .......+ k^2 > k^3/3`............(1)

We shall now prove that P(k + 1) is true whenever P(k) is true.
We have `1^2 + 2^2 + 3^2 + ... + k^2 + (k + 1)^2`

`= (1^2+ 2^2 + .... + k^2) + (k+1)^2 > k^3/3 + (k+1)^2` [by (1)]

`=1/3 [k^3+ 3k^2 + 6k +3]`

`=1/3 [ (k+1)^3 + 3k +2] > 1/3 (k+1)^3`

Therefore, P(k + 1) is also true whenever P(k) is true. Hence, by mathematical induction
P(n) is true for all n ∈ N.
Q 3145745663

Prove the rule of exponents `(ab)^n = a^n b^n`
by using principle of mathematical induction for every natural number.

Solution:

Let P(n) be the given statement

i.e. `P(n) : (ab)^n = a^n b^n`.

We note that P(n) is true for n = 1 since `(ab)^1 = a^1b^1`.

Let P(k) be true, i.e.,

`(ab)^k = a^k b^k` ... (1)

We shall now prove that P(k + 1) is true whenever P(k) is true.

Now, we have

`(ab)^(k + 1) = (ab)^k (ab)`

`= (a^k b^k) (ab)` [by (1)]

`= (a^k . a^1) (b^k . b^1) = a^(k+1) . b^(k+1)`

Therefore, P(k + 1) is also true whenever P(k) is true. Hence, by principle of
mathematical induction, P(n) is true for all n ∈ N.
 
SiteLock